package codetop.microsoft.T92;

import util.ListNode;

/**
 * @Author: 18362
 * @Create: 2022-09-04 22:35:54 星期日
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null)
            return head;
        if (left == 1)
            return reverseK(head, right - left + 1);
        ListNode p = head;
        for (int i=1; i<left-1; ++i)
            p = p.next;
        p.next = reverseK(p.next, right - left + 1);
        return head;
    }

    private ListNode reverseK(ListNode head, int k) {
        if (k == 1)
            return head;
        ListNode tHead = reverseK(head.next, k - 1);
        ListNode tail = head.next;
        head.next = tail.next;
        tail.next = head;
        return tHead;
    }
}
